home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 7988 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.2 KB
  1. Path: anvil.ugrad.cs.ubc.ca!not-for-mail
  2. From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: line intersection in C
  5. Date: 28 Feb 1996 11:46:01 -0800
  6. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  7. Message-ID: <4h2bdpINNe7h@anvil.ugrad.cs.ubc.ca>
  8. References: <1996Feb25.230142.29689@dcs.warwick.ac.uk> <3134933A.AB9@computek.net>
  9. NNTP-Posting-Host: anvil.ugrad.cs.ubc.ca
  10.  
  11. In article <3134933A.AB9@computek.net>,
  12. robert jacobs and jason jacobs  <robertj@computek.net> wrote:
  13.  >Daniel Castillo Molero wrote:
  14.  >> 
  15.  >> Hello,
  16.  >> 
  17.  >> I wonder if anybody can help me to find an algorithm in C to detect whether
  18.  >> two line segments intersect properly (I don't know if this is the correct
  19.  >> terminology, but by proper intersection I mean that the intersection is
  20.  >> not in the extreme of any of them and that one does not lie on top of
  21.  >> the other).
  22.  >> I need to test intersection just for line segments whose slope is a multiple
  23.  >> of 45 degrees, which I suppose may simplify the solution.
  24.  >> 
  25.  >> I would greatly appreciate any sort of help.
  26.  >> 
  27.  >> Daniel Castillo.
  28.  >> 
  29.  >> danmol@dcs.warwick.ac.uk
  30.  >> 
  31.  >> --
  32.  >> * Daniel Castillo.  D.C.Molero@dcs.warwick.ac.uk *
  33.  >
  34.  >Plug the end points of line segements into the equation for a line.
  35.  >Calculate the slope of the lines.  If the slopes are defferent the lines 
  36.  >will intersect.
  37.  
  38. This is a poor approach. No such representation exists for vertical lines,
  39. which have an undefined slope.
  40.  
  41. An implicit equation representation is much better, because it can represent
  42. any lines:
  43.  
  44.     Ax + By = C
  45.  
  46. This can represent vertical lines (just set B = 0), horizontal lines (set A =
  47. 0) and everything in between using finite constants for A and B.
  48.  
  49.  
  50. Furthermore, (A, B) forms a vector that is perpendicular to the line, and when
  51. you rotate this vector by 90 degrees, you get one that is parallel to the
  52. line: the rule is, swap the coordinates and negate one of them: (-B, A)
  53.  
  54. If you find the parallel vector of one line and the perpendicular vector of
  55. another line, and take their dot product, it is zero if the two vectors are
  56. perpendicular which is if and only if the two lines intersect somewhere.
  57. -- 
  58.  
  59.